package com.lwl.leetcode;

import org.junit.Test;

import java.util.LinkedList;

/**
 * @author lwl
 * @Description TODO
 * @date 2023/8/1 10:48
 */
public class Code42Trap {
    public int trap(int[] height) {
        if (height == null || height.length == 0) {
            return 0;
        }
        LinkedList<Integer> stack = new LinkedList<>();
        int res = 0;
        for (int i = 0; i < height.length; i++) {
            while (!stack.isEmpty() && height[i] > height[stack.peekLast()]) {
                Integer pollIndex = stack.pollLast();
                if (!stack.isEmpty()) {
                    int leftIndex = stack.peekLast();
                    int rightIndex = i;
                    int curHeight = Math.min(height[leftIndex], height[rightIndex]) - height[pollIndex];
                    res += curHeight * (rightIndex - leftIndex - 1);
                }
            }
            stack.add(i);
        }
        return res;
    }

    @Test
    public void test() {
        System.out.println(trap(new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}));
        System.out.println(trap(new int[]{4, 2, 0, 3, 2, 5}));
    }
}
